5880. МEX
Do you know how hard it is – to pull the
trigger?
The infamous dictator Li Siy Sun commands
an army of 105 soldiers. He numbered them from 0 to 105 –
1: the smaller the number, the greater the soldier’s command abilities. Later,
he repressed n of them. Now the dictator is preparing to wage a small
victorious war against a neighboring state, so he urgently needs to choose the
most talented military officer among those who are still alive.
Input. The first line contains the number of repressed
soldiers n (1 ≤ n < 105). The second line
lists their indices in Li Siy Sun’s roster – all numbers are less than 105.
Output. Print one number – the index of the most talented
surviving soldier.
|
Sample
input |
Sample
output |
|
8 3 0 1 7 2 4 6 17 |
5 |
SOLUTION
counting sort
Algorithm analysis
Let cnt be an integer array of
length 105. For each value x
from the input list of repressed individuals, set cnt[x] = 1.
Then we need to find the
smallest index i for which cnt[i] = 0. This number is the
smallest one that does not appear in the input data. This i will be the
number of the most talented military officer among those who survived.
Example
Let us look at the state
of the cnt
array after processing all the data from the input test.
The smallest number
missing from the input array is 5, because cnt[5] = 0.
Algorithm implementation
Declare an
array to keep track of the numbers that appear in the input data.
#define MAX 100001
int cnt[MAX];
Read the input data. For each value x
from the list of repressed individuals, set cnt[x] = 1.
scanf("%d", &n);
for (i = 0; i < n; i++)
{
scanf("%d", &x);
cnt[x] = 1;
}
Next,
search for the smallest non-negative integer that is missing from the input
list. To do this, we need to find the smallest i (i ≥ 0) such that cnt[i] = 0.
for (i = 0; i < MAX; i++)
if (cnt[i] == 0)
{
printf("%d\n", i);
break;
}